1. Field of the Invention
The present invention relates to a technology adapted to generate signature data that can be stored over a long term for transmitted digital data and verify the signature data.
2. Description of the Related Art
In recent years, digital data on a document and/or an image is distributed via a wide-area network such as the Internet. However, since the digital data can be easily modified, the digital data may be altered by a third party. Therefore, a digital-signature technology has been proposed as a method for verifying padding data used for preventing alteration. According to the digital-signature technology, a user can detect whether or not data transmitted thereto is altered. The digital-signature technology is adapted to prevent not only data alteration, but also spoofing, repudiation, and so forth on the Internet.
[Digital Signature]
Digital-signature data is generated by using a hash function and a public-key cryptosystem. More specifically, first, a private key Ks and a public key Kp are prepared. Then, on the transmission side, transmission data M is subjected to hash processing so that fixed-length data H(M) is calculated, and the fixed-length data H(M) is converted by using the private key Ks so that digital-signature data S is generated. After that, the digital-signature data S and the transmission data M are transmitted to the reception side.
On the reception side, the digital-signature data S is converted (decoded) by using the public key Kp. Then, it is determined whether or not the converted data agrees with data obtained by subjecting the transmission data M to the hash processing. If the verification result shows that the converted data does not agree with the data obtained by subjecting the transmission data M to the hash processing, it is determined that the transmission data M is altered.
The digital signature is generated by using a known public-key-cryptosystem method such as the RSA method, the DSA method, and so forth. According to the above-described methods, the security of a digital signature is ensured based on the premise that it is difficult for an entity other than the owner of the private key to substitute the signature and/or decipher the private key from the viewpoint of calculation quantity.
FIG. 1 shows the signing-process performed for generating the above-described digital-signature data and the verifying-process performed for verifying transmission data by using the digital-signature data.
[Hash Function]
Next, the hash function used for increasing the speed of generating the digital-signature will be described. The hash function is used for processing the transmission data M of an arbitrary length so that output data of a predetermined length is generated. Here, output data H(M) is referred to as hash data of plain-text data M. Particularly, where a one-way hash function is used and the plain data M is provided, it is difficult to calculate plain-text data M′, where the expression H(M′)=H(M) holds, from the viewpoint of calculation quantity. Here, there are standard algorithms including MD2, MD5, SHA-1, and so forth that can be used, as the one-way hash function. The above-described algorithms are in public view.
[Public-Key Cryptosystem]
Next, the public-key cryptosystem will be described. The public-key cryptosystem uses two different keys, where data encrypted by using one of the keys is decrypted only by using the other key. One of the two keys is referred to as a public key and released, so as to be in public view. The other key is referred to as a private key and is controlled only by the owner thereof.
A digital signature using the above-described public-key-cryptosystem method may be, for example, a DSA signature, an RSA signature, a Schnorr signature, and so forth. Hereinafter, the DSA signature will be described, as an example digital signature.
[DSA Signature]
Next, a method disclosed in “Federal Information Processing Standards (FIPS) 186-2, Digital Signature Standard (DSS), January 2000”, will be described. Each of parameters p and q denotes a prime number, where the prime number q is divisible by p−1. A specifier g is determined to be an element of order q (generator), where the element is arbitrarily selected from among a group Z_p* (a multiplicative group obtained by subtracting 0 from a cyclic group Z_p of the order p. Data x arbitrarily selected from the multiplicative group Z_p* is determined to be a private key and the public key y corresponding to the private key is shown by the expression y:=gx mod p. The specifier H( ) denotes the hash function.
[DSA-Signature Generation]
Procedural steps performed for generating the signature corresponding to a document M is shown below:
1) α is arbitrarily selected from Z_q, where the expression T:=(gα mod p) mod q holds.
2) The expression c:H(M) holds.
3) The expression s:α−i(c+xT) mod q holds, where (S, T) is determined to be signature data.
[DSA-signature Verification]
Procedural steps performed for verifying the signature data (s, T) for the document M will be described. It is verified whether or not the expression T=(gH(M)/syT/s mod p) mod q holds.
As has been described, the digital-signature technology can prevent spoofing, data alteration, repudiation, and so forth on the Internet. Further, the safety of the digital signature is often ensured based on the premise that it is difficult for an entity other than the owner of the private key to counterfeit the signature and/or decipher the private key, from the viewpoint of the calculation quantity. The above-described DSA-signature technology is one of signature methods configured to ensure the safety of a digital signature based on the premise that a large quantity of calculations are required for counterfeiting the signature and/or deciphering the private key.
On the other hand, in the fields of administration, health care, and so forth, a digital signature is required by law to be stored over a long term such as five or ten years. However, the currently used digital-signature technologies have problems (1) and (2) that will be described later, so that a technology adapted to store a signature over a long term, namely, a system configured to ensure the authenticity of the signature over the long term is required. The above-described system is supposed to be used, particularly with an electronic-authentication system and a time-stamping system in combination.
(1) A digital signature cannot be stored over a long term in the unit of ten years due to advanced deciphering technologies and computers of increased performance.
(2) A public key and/or a private key with an expired public-key certificate may be used for checking the validity of a digital signature.
As a method adapted to solve the above-described problems (1) and (2), a signature method on the basis of information theoretic security has been disclosed in, for example, “G. Hanaoka, J. Shikata, Y. Zheng, and H. Imai, Unconditionally secure digital signature schemes admitting transferability, Advances in Cryptology—ASIACRYPT 2000, LNCS 1976, pp. 130 to 142, Springer—Verlag, 2000”. According to the above-described technology, the security of a signature can be ensured without depending on the calculation quantity.
However, the above-described signature technology is still in a studying stage toward commercialization. Further, the concept of the above-described signature technology was not known up until the recent past and has room to be studied. Still further, the above-described signature technology has problems such that there is no compatibility between the above-described signature technology and the known signature technologies that have been used.